1. Field of the Invention
The present invention generally relates to designing routes for interconnecting electrical components, and more particularly, to methods and apparatuses for routing interconnections between terminals of electrical components mounted on or fabricated in a substrate, board, or package.
2. Description of the Related Art
The technology of integrated circuits has progressed rapidly. Advances in the design and manufacture of integrated chips has increased the number of transistors on a chip from around 30 on early chips to the current very large scale integrated circuits having over 3 million transistors. Despite the advances in design and manufacturing techniques, however, the packaging and interconnection technologies have not progressed so quickly.
Conventional packaging involves enclosing bare dies of integrated chips in plastic or ceramic packages, which are then mounted on a printed circuit board (PCB). The packaged circuits are then interconnected on the PCB.
Although PCBs are effective for many applications, they provide limited density. In addition, relatively long wires interconnect the chips in PCBs, causing unacceptably long propagation delays for some high performance applications. To provide greater density and improved performance. many designers use multichip modules (MCMs) as an alternative packaging and interconnection system. MCMs bypass the single chip package by mounting bare dies directly onto a routing substrate. Eliminating chip packaging typically provides much denser assemblies as well as shorter and faster interconnects. In spite of the improved size, weight, speed, and power consumption MCMs offer over conventional PCBs, however, design obstacles, especially the physical design of the MCM, frequently engender high costs. In particular, the physical design of an MCM presents a technical, complex, and often costly process of laying out the components and interconnecting them, subject to various physical, thermal, and electrical constraints.
Although advances in the physical design of PCBs and integrated chips facilitated faster and better circuits and boards, the design tools used for PCBs and integrated circuits are often unsuitable for MCMs. MCM designs are typically too dense and complex for PCB design tools, and integrated circuit layout tools use different geometrical and electrical constraints. As a result, various researchers and industries have generated a variety of products and schemes dedicated to MCM design. The MCM physical design process presents a truly three dimensional challenge, as it includes multiple layers of interconnections beneath the top layer. Objectives in MCM design typically include minimizing the number of layers, minimizing the number of vias (vertical connections between layers through intervening insulative layers), minimizing total wire length, and satisfying electrical constraints such as timing considerations and crosstalk. Various types of design tools aim to achieve these objectives with varying degrees of success.
For example, maze routing is a well known technique, designed to seek a path between two points in a rectangular or box-like grid while avoiding obstacles. The implementation of maze-type systems, however, is limited to net-by-net routing, so that the order in which nets are routed may radically affect the resulting routing solution. Thus, establishing an appropriate net routing order is vital, though effective tools for doing so have yet to be developed. in addition, searching all of the available grid points for acceptable routes requires substantial processing time and considerable memory in the analyzing system, demanding sophisticated hardware. Further, maze routing tends to induce multiple vias because some nets are routed through several layers, and the net-by-net process limits the global optimization of the design. Several variations of maze routing tools have been developed, and substantially all of them suffer these shortcomings to some degree.
Some systems avoid net ordering, improving the performance of the design tool. Nonetheless, such design tools cannot easily incorporate electrical constraints and the like into the design. In addition, further improvements in density, via minimization, and wire length reduction are desirable. In sum, it would be advantageous to develop a routing system without net ordering problems incorporate other considerations, such as electrical constraints, into the design, and maintain high density routing solutions.
A routing system according to various aspects of the present invention comprises a computer system for generating candidate routes and analyzing them for compatibility. The routing system employs a global approach to generate several candidate routes before analyzing them for compatibility. Incompatible routes are then selectively deleted from the configuration to arrive at a fully compatible set of routes. The process reiterates to generate further compatible routes using different candidate routes and routes of different complexity. Ultimately, the process arrives at a fully compatible set of routes, or adds further layers as may be necessary to accommodate all of the nets. The process is then repeated for the new layer pair until all of the nets are routed. A post-routing procedure may also be implemented to further simplify the routing solution.
A routing system according to various aspects of the present invention initially generates routes without regard to potential conflicts with other candidates, thus avoiding net ordering problems. In addition, the designer is allowed to select the topology of the routes. Further, electrical considerations, such as crosstalk potential or timing constraints, may be incorporated into the analysis and routing system. The present routing system provides enhanced routing solutions by minimizing the number of layers, vias, and wire length, and improving overall density.